package _4_algorithms;

import org.junit.Test;

import java.util.Arrays;

public class 线性表结构 {

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        Node node = reverseList2(head);
    }

    //⽤用递归的⽅方法反转链表
    public static Node reverseList2(Node head) {
        // 1.递归结束条件
        if (head == null || head.next == null) {
            return head;
        }
        // 递归反转 链表
        Node newList = reverseList2(head.next);
        // 改变 1，2节点的指向。
        // 通过 head.next获取节点2
        Node t1 = head.next;
        // 让 2 的 next 指向 2
        t1.next = head;
        // 1 的 next 指向 null.
        head.next = null;
        // 把调整之后的链表返回。
        return newList;
    }

    private static class Node {
        int data;
        Node next;

        public Node(int i) {
            data = i;
        }
    }

    /**
     * 一个数组元素在 [1, n] 之间，其中一个数被替换为另一个数，找出重复的数和丢失的数
     * 如：[2,4,1,1]   重复的是1, 丢失的是3
     */
    @Test
    public void findErrorNums() {
        int[] nums = {1, 4, 5, 3, 2, 6, 7, 9, 10, 10};
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
                System.out.println(Arrays.toString(nums));
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                System.out.println(nums[i] + "," + (i + 1));
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}
